#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void _quick_sort(int* arr,size_t left,size_t right)
{
	if(left >= right) return;

	// 计算标杆的下标
	int pi = (left+right)/2;
	// 备份标杆的值
	int pv = arr[pi];
	// 备份左右下标
	int l = left , r = right;
	// 左右下标相遇时结束
	while(l < r)
	{
		// 在标杆的左边寻找比它大的数据
		while(l<pi && arr[l] <= pv) l++;
		if(l<pi) // 如果没有超出范围，说明找到比标杆大的值
		{
			// 与标杆交换位置，并记录新的标杆下标
			arr[pi] = arr[l];
			pi = l;
		}
		// 在标杆的右边寻找比它小的数据
		while(pi<r && arr[r] >= pv) r--;
		if(pi<r) // 如果没有走出范围，说明找到比标杆小的值
		{
			arr[pi] = arr[r];
			pi = r;
		}
	}
	// 还原标杆的值
	arr[pi] = pv;
	if(pi-left > 1) _quick_sort(arr,left,pi-1);
	if(right-pi > 1) _quick_sort(arr,pi+1,right);
}

void quick_sort(int* arr,size_t len)
{
	_quick_sort(arr,0,len-1);
}

void show_arr(int* arr,size_t len)	//显示函数
{
	for(int i=0; i<len; i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[10];

	for(int i=0; i<10; i++)
	{
		arr[i] = rand() % 100;
	}
	show_arr(arr,10);			//显示初始数组
	quick_sort(arr,1000);		//进行冒泡排序
	show_arr(arr,10);			//显示排序后的数组

}
